/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;



/**
 * @ClassName   : Leetcode0127 
 * @author      : ganwei 
 * @date        : 2020年5月26日
 * @Description : Leetcode0127 单词接龙
 */
public class Leetcode0127 {
    /**
     * -解题思路，广度优先遍历,单项的超时
     */
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(wordList.contains(endWord)){
        	return 0;
        }
        
        Map<String, Boolean> visited = new HashMap<String, Boolean>();
		Queue<String> q = new LinkedList<String>();
		q.offer(beginWord);
		visited.put(beginWord, true);
		
		int path = 0;
		while(!q.isEmpty()){
			int length = q.size();
			for(int i = 0; i < length; i++){
				String s = q.poll();
				visited.put(s, true);
				if(s.equals(endWord)){
					return path;
				}
				for(String ss : wordList){
					if(canTransfer(s,ss) && !visited.getOrDefault(ss, false)){
						q.offer(ss);
						wordList.remove(ss);
					}
				}
			}
			path++;
		}
		
		
		return 0;
    }
	
	public boolean canTransfer(String s1, String s2){
		int index = 0;
		int cnt = 0;
		while(index < s1.length()){
			if(s1.charAt(index) != s2.charAt(index)){
				cnt++;
			}
			index++;
		}
		return cnt == 1;
	}

	public static void main(String[] args){
		Leetcode0127 l0127 = new Leetcode0127();
		System.out.println(l0127.canTransfer("gan", "gb3"));
		List<String> l = new ArrayList<String>();
		l.add("gan");
		l.add("wei");
		for(String s : l){
			System.out.println(s);
			l.remove(s);
		}
		
	}
}
